

let testArr = [1,3,6,7,7,8,99,123,555,555,666,2233]

/**
 * 适合查找有序的数组
 * 每次从中间位置比较, 比目标数字大就往右走，比目标数字小，就往左走
 */
function binarySearch(item, arr) {
    let max = arr.length - 1
    let min = 0
    while (max >= min){
        let mid = Math.floor((max+min)/2)
        if (item === arr[mid]){
            return mid
        }
        if (item > arr[mid]){
            min = mid + 1 // arr[mid] 比target大，target可能在[mid + 1, max] 之间，mid 不用重复比较了，所以要加一
        }else {
            max = mid - 1 // arr[mid] 比target小，target可能在[min, mid - 1] 之间，mid 不用重复比较了
        }
    }
    return -1
}

console.log(binarySearch(123, testArr))

// 查找最后一个值等于给定值的元素
function bsearch2(item, arr) {
    let min = 0
    let max = arr.length - 1
    while (min <= max){
        let mid = min + Math.floor((max-min)/2)
        if (arr[mid] > item){
            max = mid - 1
        }else if (arr[mid] < item) {
            min = mid + 1
        }else {
            if (mid === arr.length - 1||arr[mid+1]!==item){
                // mid是数组最后一个元素了，肯定是最后一个等于item的
                // 或者 arr[mid] 下一个数 ！== item , 那 mid 就是最后一个
                return mid
            }else {
                // 否则继续找，最后一个等于item 的肯定 > mid
                min = mid + 1
            }
        }
    }
    return -1
}

console.log("bs2", bsearch2(7,testArr))

// 查找第一个值大于或等于给定值的元素
function bs3(item, arr) {
    let min = 0
    let max = arr.length - 1
    while (min <= max){
        let mid = min + Math.floor((max-min)/2)
        if (item > arr[mid]){
            min = mid + 1
        }else { // 不小于就是大于或等于
            if (mid === 0 || arr[mid - 1] < item){
                return mid
            }else {
                max = mid - 1
            }
        }
    }
}

console.log("bs3", bs3(9, testArr))

// 查找最后一个值小于或等于给定值的元素
function bs4(item, arr) {
    let min = 0
    let max = arr.length - 1
    while (min<=max){
        let mid = min + Math.floor((max-min)/2)
        if (arr[mid] > item){
            max = mid - 1
        }else {
            if (mid === arr.length || arr[mid + 1]>item){
                return mid
            }else {
                min = mid + 1
            }
        }
    }
}
console.log("bs4",bs4(11, testArr))